package dataStructure.sort.radixSort;

import java.util.Arrays;

/**
 * @author lhn
 * @date 2024-09-01 15:29
 */

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));

        sort(arr);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        //获得数组中最大数的位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }
        int maxLength = (max + "").length();

        for (int i = 0; i < maxLength; i++) {

            //第一轮对10取模，得到个位数的数
            int[][] bucket = new int[10][arr.length];   //10个桶
            int[] bucketElementCounts = new int[10];    //存储每个桶中元素的个数
            for (int j = 0; j < arr.length; j++) {
                int digit = (int) (arr[j] / (Math.pow(10, i)) % 10); //个位数
                bucket[digit][bucketElementCounts[digit]] = arr[j];
                bucketElementCounts[digit] ++;
            }
//            System.out.println("=====================");
//            for (int[] bucketElement: bucket
//            ) {
//                System.out.println(Arrays.toString(bucketElement));
//            }
//            System.out.println("=====================");
//            System.out.println(Arrays.toString(bucketElementCounts));

            int index = 0;
            //遍历bucketElementCounts
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果bucketElementCounts[k] != 0，说明k对应的桶中有数据
                if (bucketElementCounts[k] != 0) {
                    //循环该桶，将数据放入arr
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index] = bucket[k][l];
                        index ++;
                    }
                }
                bucketElementCounts[k] = 0;
            }
            System.out.println("第" + i + "轮排序后：");
            System.out.println(Arrays.toString(arr));
        }

    }
}
